package features.advance.leetcode.dynamicProgramming;

import java.util.Arrays;

/**
 *  628. 三个数的最大乘积
 *
 *  难度：简单
 *
 * 给你一个整型数组 nums ，在数组中找出由三个数组成的最大乘积，并输出这个乘积。
 *
 *
 *
 * 示例 1：
 *
 * 输入：nums = [1,2,3]
 * 输出：6
 * 示例 2：
 *
 * 输入：nums = [1,2,3,4]
 * 输出：24
 * 示例 3：
 *
 * 输入：nums = [-1,-2,-3]
 * 输出：-6
 *
 *
 * 提示：
 *
 * 3 <= nums.length <= 104
 * -1000 <= nums[i] <= 1000
 *
 * @author LIN
 * @date 2021-05-25
 */
public class Solution628 {

    public static void main(String[] args) {
        Solution solution = new Solution() {
            // 找到三个最大的正数，两个最小的负数，计算负数和最大正数的乘积，三个正数的乘积
            @Override
            public int maximumProduct(int[] nums) {
                // 最小的和第二小的
                int min1 = Integer.MAX_VALUE, min2 = Integer.MAX_VALUE;
                // 最大的、第二大的和第三大的
                int max1 = Integer.MIN_VALUE, max2 = Integer.MIN_VALUE, max3 = Integer.MIN_VALUE;

                for (int x : nums) {
                    if (x < min1) {
                        min2 = min1;
                        min1 = x;
                    } else if (x < min2) {
                        min2 = x;
                    }

                    if (x > max1) {
                        max3 = max2;
                        max2 = max1;
                        max1 = x;
                    } else if (x > max2) {
                        max3 = max2;
                        max2 = x;
                    } else if (x > max3) {
                        max3 = x;
                    }
                }
                return Math.max(min1 * min2 * max1, max1 * max2 * max3);
            }
        };
        solution = new Solution(){
                @Override
                public int maximumProduct(int[] nums) {
                    int max1 = Integer.MIN_VALUE,
                            max2 = Integer.MIN_VALUE,
                            max3 = Integer.MIN_VALUE,
                            min1 = Integer.MAX_VALUE,
                            min2 = Integer.MAX_VALUE;
                    for(int x : nums){
                        if(x > max3){
                            max3 = x;
                            if(x > max2){
                                max3 = max2;
                                max2 = x;
                                if(x > max1){
                                    max2 = max1;
                                    max1 = x;
                                }
                            }
                        }
                        if(x < min2){
                            min2 = x;
                            if(x < min1){
                                min2 = min1;
                                min1 = x;
                            }
                        }
                        //System.out.println(max1+" " + max2+" "+max3+" "+min1+" " +min2);
                    }

                    return Math.max((max1 * max2 * max3),
                            (max1 * min1 * min2));
                }
        };

        int[] nums = {-100,-98,-1,2,3,4};
        int res = solution.maximumProduct(nums);
        System.out.println(res);
    }

    static class Solution{
        /**
         *  三个数不连续的
         * @param nums
         * @return
         */
        public int maximumProduct(int[] nums){
            if(nums == null || nums.length < 3) return 0;
            int max = nums[0] * nums[1] * nums[2];
            if(nums.length == 3) return max;
            // 排序时间复杂度NlogN
            Arrays.sort(nums);
            int length = nums.length;
            return Math.max(nums[length-3]*nums[length-2]*nums[length-1], Math.max(max,nums[0]*nums[1]*nums[length -1]));
        }
    }
}



